那接下來我們就要解釋什麼是時間複雜度和 Big O !

時間複雜度(Time Complexity)

時間複雜度就是工程師可以根據演算法 執行次數 來 衡量執行時間的標準
現在定義一個 T(n) 表示程式執行的時間，n 為資料輸入量

我們的目標是找出程式碼中的「基本操作（Basic Operation）」，並計算它隨著 n 的變大會執行幾次。

舉例來說:

int sum = 0;                   // 執行 1 次
for (int i = 0; i < n; i++) {  // 迴圈跑 n 次
    sum += 1;                  // 執行 n 次
}

那根據我們定義的 T(n)= n + 1 (宣告sum的一次 + 迴圈的n次)
又或者是

for (int i = 0; i < n; i++) {       // 外層跑 n 次
    for (int j = 0; j < n; j++) {   // 內層跑 n 次
        count++;
    }
}

那為什麼我們要用Big O表示，不用T(n)呢?
因為 T(n) 是精準到每一步都要計算
可是當你程式的資料量 n 多到像 10^6 那麼大的時候，其實後面的數字(常數項、低次方項)也就無足輕重

舉例來說:

那當我們n趨近於無限大的時候，其實 2n+1 就可以忽略不記
用Big O表示會變成 O(n^3)

補充 :
其實有很多種表示方法 (漸進符號)，一個是常見的Big O，另外兩個是Ω−
Notation，和Θ− Notation，
或是o−Notation 與ω−Notation。
有興趣的話可以觀看下列文章，我覺得講解的滿好的
Complexity：Asymptotic Notation(漸進符號)- by Chiu CC

Big O

大O符號 (Big O notation )是用來衡量演算法執行的時間或記憶體空間隨資料量 n
成長的趨勢

圖片來源: https://medium.com/@buketsenturk/time-complexity-202eb4f1db40

Big O有三個要點

1. 去掉常數項
2. 去掉低次方項
3. 去掉係數

這邊就來簡單解釋一下

1. 去掉常數

   常數項是指跟 n 完全無關、不會因為資料量變大而增加的固定次數。
   例如 T(n) = n + 5,
   不管 n 是 100 還是 1000000,那個 +5 永遠只加一次,跟 n 的成長速度比起來,常數的影響會被越來越大的 n 徹底稀釋掉
   所以直接省略,寫成 O(n)

2. 去掉低次方項

   當一個式子裡同時有好幾個不同次方的項時,只留下成長最快的那一項。
   例如: T(n) = n^2 + n,
   當 n 很大時(比如 n = 10000),
   n^2 是 100,000,000,而 n 只有 10,000,相差一萬倍,
   n 這一項相對來說幾乎可以忽略,所以只保留 n^2
   ,寫成 O(n^2)。

3. 去掉係數

   例如 T(n) = 3n跟 T(n) = 100n,
   雖然常數倍數差很多,但兩者都是隨著 n 線性成長,
   成長的「型態」是一樣的,所以 Big O 只在乎成長的數量級,不在乎前面乘了幾倍,兩者都寫成 O(n)。

這邊來看以下幾個例子方便弄懂

O(1) :

int a[10];
cout<<a[0];

執行一次
所以為 O(1)

O(n) :
將資料全部看一遍

for(int i=0;i<n;i++){
   cout<<a[i]<<" "; 
}

共執行n次
所以為 O(n)

O(log n) :
Binary search(二分搜)

int left=0,right=n-1;
while(left<=right){
    int mid=(left+right)/2;
    if(arr[mid]==target){
        return mid;
    }
    if(arr[mid]<target){
        left=mid+1;
    }else{
        right=mid-1;
    }
}

每次執行的時候， n 如果沒達成條件就會一直除2直到不能除

n
n/2
n/4
n/8
.
.
.
1

那我們可以把他記為 O(log n)

O(nlog n) :
merge sort

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

因為每次都把資料切一半，所以總共會切出 log₂n 層；
而在合併的過程中，每一層都需要將所有元素掃描一次，
因此每層的成本為 O(n)。

總時間為：

O(n) × O(log n)
= O(n log n)

搭配下面影片更好懂~

O(n^2) :

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        ans++;
    }
}

外層跑n次
內層跑n次
所以是 n*n
O(n^2)

O(2^n) :
費波納契數列遞迴

int fib(int n) {
    if (n <= 1)
        return n;
    
    return fib(n - 1) + fib(n - 2);
}

假設 fib(5)
那可以接著計算

fib(5)
= fib(4) + fib(3)

fib(4)
= fib(3) + fib(2)

fib(3)
= fib(2) + fib(1)

fib(2)
= fib(1) + fib(0)

那我們可以發現
fib(3)，被計算不只一次
然後fib(2)被算了更多次
所以當 n增加時，被呼叫的次數會快速成長

所以我們通常可以把這類演算法的時間複雜度記為 O(2^n)$

這篇意外的寫得有點多>< 那明天我們會來介紹空間複雜度(Space complexity)，那上述的程式之後有機會的話應該會把它拿出來補充得更清楚一點

參考資料

1. 圖解資料結構×演算法:運用C++ 胡昭明
2. https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80
3. https://pjchender.dev/dsa/algo-intro/
4. https://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html
5. https://www.youtube.com/watch?v=3j0SWDX4AtU